package stmo.树.B树;

/**
 *      B树
 *
 *      本质上是对2-3树的扩展
 *
 *      B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。
 *
 *      选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：
 *      每个结点最多有M-1个key，并且以升序排列；
 *      每个结点最多能有M个子结点；
 *      根结点至少有两个子结点；
 *
 *      在实际应用中B树的阶数一般都比较大（通常大于100），所以，即使存储大量的数据，B树的高度仍然比较小，这
 *      样在某些应用场景下，就可以体现出它的优势。即查询效率高
 *
 *
 *      B+树
 *
 *      B+树是对B树的一种变形树，它与B树的差异在于：
 *      1. 非叶结点仅具有索引作用，也就是说，非叶子结点只存储key，不存储value；
 *      2. 树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据。
 *
 *      B+树和B树的对比：
 *
 *      B+ 树的优点在于：
 *      1.由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。
 *      2.B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，
 *      所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。(即叶子结点是排序好的，且相连构成链表)
 *
 *      B树的优点在于：
 *      由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到
 *      value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶
 *      子结点的深度，才能找到value。(B+树索引的地方为需要查找的数据，还需要继续查找，B树不用)
 *
 *      B+树在数据库中的应用
 *      在数据库的操作中，查询操作最频繁的一种操作，在设计数据库时，考虑到查询的效率问题，
 *      很多数据库中，用到了B+树来提高查询的效率；
 *
 *      区间查询
 *      执行 select * from user where id>=12 and id<=18 ,如果有了索引，由于B+树的叶子结点形成了一个有序链表，
 *      所以我们只需要找到id为12的叶子结点，按照遍历链表的方式顺序往后查即可，效率非常高。
 *
 */
public class BTree {


}
